home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / viewkit / xcontact / parody / btree.c++ next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  13.2 KB  |  506 lines
  1. // ---------------- btree.cpp
  2.  
  3. #include <string.h>
  4. #include "parody.h"
  5.  
  6. // ---------- constructor to open a btree
  7. Btree::Btree(Index& ndx, Key *ky) :
  8.                 index(ndx), LinkedListEntry(NULL)
  9. {
  10.     currnode = 0;
  11.     trnode = NULL;
  12.     nullkey = ky->Make();
  13.     nullkey->Key::operator=(*ky);
  14.     NodeNbr nd = 0;
  15.     int clno = ky->classid;
  16.  
  17.     if (!index.NewFile())    {
  18.         Node node(&index, 1);
  19.         // ------- locate the class header
  20.         while (clno)    {
  21.             NodeNbr nx = node.NextNode();
  22.             if (nx == 0)    {
  23.                 // need to link this one with new one(s) added
  24.                 nd = index.NewNode();
  25.                 node.SetNextNode(nd);
  26.                 break;
  27.             }
  28.             node = Node(&index, nx);
  29.             --clno;
  30.         }
  31.         if (clno == 0)    {
  32.             // ------ position to the tree header
  33.             index.Nfile().seekg((long)
  34.                 (ky->indexno * sizeof(TreeHeader)), ios::cur);
  35.             headeraddr = index.Nfile().tellp();
  36.             // ------- read the btree header
  37.             index.Nfile().read((char *)
  38.                         &header, sizeof(TreeHeader));
  39.             return;
  40.         }
  41.     }
  42.     // ------- build the class headers for new node or class
  43.     index.ResetNewFile();
  44.     if (nd == 0)
  45.         nd = index.NewNode();
  46.     else
  47.         --clno;
  48.     TreeHeader th;
  49.     const int treect = nodedatalength / sizeof(TreeHeader);
  50.     while (clno)    {
  51.         Node node(&index, nd);
  52.         for (int i = 0; i < treect; i++)
  53.             index.Nfile().write((char*)&th,sizeof(TreeHeader));
  54.         nd = index.NewNode();
  55.         node.SetNextNode(nd);
  56.         --clno;
  57.     }
  58.  
  59.     Node node(&index, nd);
  60.     // ------ position to the tree header
  61.     for (int i = 0; i < ky->indexno; i++)
  62.         index.Nfile().write((char *)&th, sizeof(TreeHeader));
  63.     headeraddr = index.Nfile().tellp();
  64.     // ------- write the btree header
  65.     index.Nfile().write((char *)&header, sizeof(TreeHeader));
  66.     // ------- pad out the rest of the node
  67.     for (i++; i < treect; i++)
  68.         index.Nfile().write((char *)&th, sizeof(TreeHeader));
  69.     // ----- pad any residual node space
  70.     int residual = nodedatalength-treect*sizeof(TreeHeader);
  71.     if (residual)    {
  72.         char *residue = new char[residual];
  73.         memset(residue, 0, residual);
  74.         index.Nfile().write(residue, residual);
  75.         delete residue;
  76.     }
  77.     node.MarkNodeChanged();
  78. }
  79.  
  80. // ---------- destructor for a btree
  81. Btree::~Btree()
  82. {
  83.     index.Nfile().seekg(headeraddr);
  84.     index.Nfile().write((char *)&header, sizeof(TreeHeader));
  85.     delete nullkey;
  86. }
  87.  
  88. // ---------------- insert a key into a btree
  89. void Btree::Insert(void *keypointer)
  90. {
  91.     // ---- don't insert duplicate keys
  92.     if (!Find(keypointer))    {
  93.  
  94.         Key *newkey = ((Key *)keypointer)->Make();
  95.         *newkey = *(Key *)keypointer;
  96.  
  97.         NodeNbr rootnode = 0, leftnode = 0, rightnode = 0;
  98.         pBool RootisLeaf = pTrue;
  99.  
  100.         pBool done = pFalse;
  101.         // -------- insert key into btree
  102.         while (currnode)    {
  103.             int em = trnode->m();
  104.             trnode->Insert(newkey);
  105.                                 // first insertion is into leaf
  106.                                 // if split, subsequent insertions
  107.                                 // are into parents (non-leaves)
  108.             if (!trnode->header.isleaf)
  109.                 trnode->currkey->lowernode = rightnode;
  110.  
  111.             done = (pBool) (trnode->header.keycount <= em);
  112.             if (!done)
  113.                 // ---- node is full, 
  114.                 //      try to redistribute keys among siblings
  115.                 done = trnode->Redistribute(
  116.                             trnode->header.leftsibling);
  117.             if (!done)
  118.                 done = trnode->Redistribute(
  119.                             trnode->header.rightsibling);
  120.  
  121.             if (done)
  122.                 break;
  123.             // ---- cannot redistribute filled node, split it
  124.             RootisLeaf = pFalse;
  125.  
  126.             rightnode = index.NewNode();
  127.             leftnode = currnode;
  128.  
  129.             TNode right(this, rightnode);
  130.             right.SetNodeNbr(rightnode);
  131.             right.MarkNodeChanged();
  132.  
  133.             // --- establish sibling and parent relationships 
  134.             //     between current node and new right sibling
  135.             right.header.rightsibling =
  136.                         trnode->header.rightsibling;
  137.             trnode->header.rightsibling = rightnode;
  138.             right.header.leftsibling = currnode;
  139.             right.header.parent = trnode->header.parent;
  140.  
  141.             // ----- if the current node is a leaf, 
  142.             //        so is the new sibling
  143.             right.header.isleaf = trnode->header.isleaf;
  144.  
  145.             // ----- compute new key counts for the two nodes
  146.             trnode->header.keycount = (em + 1) / 2;
  147.             right.header.keycount = em-trnode->header.keycount;
  148.  
  149.             // ------ locate the middle key in the current node
  150.             Key *middlekey = (Key *)
  151.                 (trnode->keys.FirstListEntry());
  152.             for (int i = 0; i < trnode->header.keycount; i++)
  153.                 middlekey = (Key *) middlekey->NextListEntry();
  154.  
  155.             // ---- set the pointer to keys less than 
  156.             //      those in new node
  157.             if (!right.header.isleaf)
  158.                 right.header.lowernode = middlekey->lowernode;
  159.  
  160.             // ----- point to the keys to move (1 past middle)
  161.             Key *movekey = (Key *) middlekey->NextListEntry();
  162.  
  163.             // ----- middle key inserts into parent
  164.             middlekey->DeleteListEntry();
  165.             *newkey = *middlekey;
  166.             delete middlekey;
  167.  
  168.             // ---- move keys from current to new right node
  169.             for (i = 0; i < right.header.keycount; i++)    {
  170.                 Key *nkey = (Key *) movekey->NextListEntry();
  171.                 movekey->DeleteListEntry();
  172.                 movekey->AppendListEntry(&right.keys);
  173.                 movekey = nkey;
  174.             }
  175.  
  176.             // ---- prepare to insert key 
  177.             //      into parent of split nodes
  178.             currnode = trnode->header.parent;
  179.             if (!currnode)    {
  180.                 // ---- no parent node, splitting the root node
  181.                 rootnode = index.NewNode();
  182.                 right.header.parent = rootnode;
  183.                 trnode->header.parent = rootnode;
  184.             }
  185.  
  186.             // --- the former right sibling of the current node
  187.             //     is now the right sibling of the split node
  188.             //     and must record the new node as left sibling
  189.  
  190.             if (right.header.rightsibling)    {
  191.                 TNode farright(this, right.header.rightsibling);
  192.                 farright.header.leftsibling = rightnode;
  193.                 farright.MarkNodeChanged();
  194.             }
  195.  
  196.             // --- children of the new split node point to
  197.             //     the current split node as parent. They must
  198.             //        be adopted by the new split node
  199.  
  200.             if (!right.header.isleaf)
  201.                 right.Adoption();
  202.  
  203.             // ----- if splitting other than root, read parent
  204.             //       position currkey to key where split node
  205.             //       key will be inserted
  206.  
  207.             if (currnode)    {
  208.                 delete trnode;    // writes the split node to disk
  209.                 // --- get the parent of the split nodes
  210.                 trnode = new TNode(this, currnode);
  211.                 // -- position currkey where new key will insert
  212.                 trnode->SearchNode(newkey);
  213.             }
  214.         }
  215.  
  216.         if (!done)    {
  217.             // ------ new root node ------ */
  218.             delete trnode;
  219.             if (rootnode == 0)
  220.                 rootnode = index.NewNode();
  221.             trnode = new TNode(this, rootnode);
  222.             trnode->header.isleaf = RootisLeaf;
  223.             currnode = header.rootnode = rootnode;
  224.             trnode->SetNodeNbr(rootnode);
  225.             trnode->Insert(newkey);
  226.             trnode->header.parent = 0;
  227.             trnode->header.keycount = 1;
  228.             if (!RootisLeaf)    {
  229.                 trnode->header.lowernode = leftnode;
  230.                 trnode->currkey->lowernode = rightnode;
  231.             }
  232.             trnode->MarkNodeChanged();
  233.         }
  234.         delete newkey;
  235.     }
  236.     delete trnode;
  237.     trnode = NULL;
  238. }
  239.  
  240. // ---------------- find a key in a btree
  241. pBool Btree::Find(void *keypointer)
  242. {
  243.     currnode = header.rootnode;
  244.     while (currnode)    {
  245.           delete trnode;
  246.               trnode = new TNode(this, currnode);
  247.  
  248.         if (trnode->SearchNode((Key *)keypointer))    {
  249.             // ---- search key is equal to a key in the node
  250.             ((Key*)keypointer)->fileaddr =
  251.                         trnode->currkey->fileaddr;
  252.             return pTrue;
  253.         }
  254.         if (trnode->header.isleaf)
  255.             break;
  256.         if (trnode->currkey == trnode->keys.FirstListEntry())
  257.             // ---- search key is < lowest key in node
  258.             currnode = trnode->header.lowernode;
  259.         else if (trnode->currkey)
  260.             // --- search key is < current key in node
  261.             currnode = ((Key *)
  262.                 (trnode->currkey->PrevListEntry()))->lowernode;
  263.         else
  264.             // --- search key is > highest key in node
  265.             currnode =
  266.             ((Key *)(trnode->keys.LastListEntry()))->lowernode;
  267.     }
  268.     return pFalse;
  269. }
  270.  
  271. // ---------------- delete a key from a btree
  272. void Btree::Delete(void *keypointer)
  273. {
  274.     if (Find(keypointer))    {
  275.         if (!trnode->header.isleaf)    {
  276.  
  277.             // --- if not found in leaf node, go down to leaf
  278.             TNode *leaf =
  279.                 new TNode(this, trnode->currkey->lowernode);
  280.             while (!leaf->header.isleaf)    {
  281.                 NodeNbr lf = leaf->header.lowernode;
  282.                 delete leaf;
  283.                 leaf = new TNode(this, lf);
  284.             }
  285.  
  286.             // ---- Move the left-most key from the leaf
  287.             //        to where deleted key was in higher node
  288.             Key *movekey = (Key *) leaf->keys.FirstListEntry();
  289.             movekey->DeleteListEntry();
  290.             leaf->header.keycount--;
  291.             leaf->MarkNodeChanged();
  292.  
  293.             movekey->InsertListEntry(
  294.                     trnode->currkey, &trnode->keys);
  295.             movekey->lowernode = trnode->currkey->lowernode;
  296.             trnode->currkey->DeleteListEntry();
  297.             delete trnode->currkey;
  298.             trnode->MarkNodeChanged();
  299.             delete trnode;
  300.  
  301.             trnode = leaf;
  302.             trnode->currkey =
  303.                 (Key *) trnode->keys.FirstListEntry();
  304.             currnode = trnode->GetNodeNbr();
  305.         }
  306.         else     {
  307.             // ---- delete the key from the node
  308.             trnode->currkey->DeleteListEntry();
  309.             delete trnode->currkey;
  310.             trnode->header.keycount--;
  311.             trnode->MarkNodeChanged();
  312.             if (trnode->header.keycount == 0)
  313.                 header.rootnode = 0;
  314.         }
  315.         // ---- if the node shrinks to half capacity,
  316.         //      try to combine it with a sibling node
  317.         while (trnode->header.keycount > 0 &&
  318.                     trnode->header.keycount <= trnode->m() / 2) {
  319.             if (trnode->header.rightsibling)    {
  320.                 TNode *right =
  321.                     new TNode(this, trnode->header.rightsibling);
  322.                 if (trnode->Implode(*right))    {
  323.                     delete right;
  324.                     NodeNbr parent = trnode->header.parent;
  325.                     if (parent == 0)    {
  326.                         header.rootnode = trnode->GetNodeNbr();
  327.                         break;
  328.                     }
  329.                     delete trnode;
  330.                     trnode = new TNode(this, parent);
  331.                     continue;
  332.                 }
  333.                 delete right;
  334.             }
  335.             if (trnode->header.leftsibling)    {
  336.                 TNode *left =
  337.                     new TNode(this, trnode->header.leftsibling);
  338.                 if (left->Implode(*trnode))    {
  339.                     delete trnode;
  340.                     NodeNbr parent = left->header.parent;
  341.                     if (parent == 0)    {
  342.                         header.rootnode = left->GetNodeNbr();
  343.                         trnode = left;
  344.                         break;
  345.                     }
  346.                     delete left;
  347.                     trnode = new TNode(this, parent);
  348.                     continue;
  349.                 }
  350.                 delete left;
  351.             }
  352.  
  353.             // --- could not combine with either sibling, 
  354.             //     try to redistribute
  355.             if (!trnode->Redistribute(
  356.                         trnode->header.leftsibling))
  357.                 trnode->Redistribute(
  358.                         trnode->header.rightsibling);
  359.             break;
  360.         }
  361.     }
  362.     delete trnode;
  363.     trnode = NULL;
  364. }
  365.  
  366. // ------ return the address of the current key
  367. Key *Btree::Current()
  368. {
  369.     if (trnode == NULL)
  370.         return NULL;
  371.     return trnode->currkey;
  372. }
  373.  
  374. // ------ return the address of the first key
  375. Key *Btree::First()
  376. {
  377.     currnode = header.rootnode;
  378.     if (currnode)    {
  379.           delete trnode;
  380.               trnode = new TNode(this, currnode);
  381.         while (!trnode->header.isleaf)    {
  382.             currnode = trnode->header.lowernode;
  383.             delete trnode;
  384.             trnode = new TNode(this, currnode);
  385.         }
  386.         trnode->currkey =
  387.             (Key *) (trnode->keys.FirstListEntry());
  388.     }
  389.     return Current();
  390. }
  391.  
  392. // ------ return the address of the last key
  393. Key *Btree::Last()
  394. {
  395.     currnode = header.rootnode;
  396.     if (currnode)    {
  397.           delete trnode;
  398.               trnode = new TNode(this, currnode);
  399.         while (!trnode->header.isleaf)    {
  400.             currnode =
  401.                 ((Key *)(trnode->keys.LastListEntry()))->
  402.                         lowernode;
  403.             delete trnode;
  404.             trnode = new TNode(this, currnode);
  405.         }
  406.         trnode->currkey =
  407.             (Key *) (trnode->keys.LastListEntry());
  408.     }
  409.     return Current();
  410. }
  411.  
  412. // ------ return the address of the next key
  413. Key *Btree::Next()
  414. {
  415.     if (trnode == NULL || trnode->currkey == NULL)
  416.         return First();
  417.     if (!trnode->header.isleaf)    {
  418.         // --- current key is not in a leaf
  419.         currnode = trnode->currkey->lowernode;
  420.           delete trnode;
  421.               trnode = new TNode(this, currnode);
  422.         // ----- go down to the leaf
  423.         while (!trnode->header.isleaf)    {
  424.             currnode = trnode->header.lowernode;
  425.               delete trnode;
  426.                   trnode = new TNode(this, currnode);
  427.         }
  428.         // ---- use the first key in the leaf as the next one
  429.         trnode->currkey =
  430.             (Key *) (trnode->keys.FirstListEntry());
  431.     }
  432.     else    {
  433.         // ------ current key is in a leaf
  434.         Key *thiskey = nullkey->Make();
  435.         *thiskey = *(trnode->currkey);
  436.  
  437.         // ----- point to the next key in the leaf
  438.         trnode->currkey =
  439.             (Key *) (trnode->currkey->NextListEntry());
  440.         while (trnode->currkey == NULL &&
  441.                         currnode != header.rootnode)    {
  442.             // --- current key was the last one in the leaf
  443.             TNode pnode(this, trnode->Parent());
  444.             pnode.SearchNode(thiskey);
  445.             currnode = pnode.GetNodeNbr();
  446.             *trnode = pnode;
  447.         }
  448.         delete thiskey;
  449.     }
  450.     return Current();
  451. }
  452.  
  453. // ------ return the address of the previous key
  454. Key *Btree::Previous()
  455. {
  456.     if (trnode == NULL || trnode->currkey == NULL)
  457.         return Last();
  458.     if (!trnode->header.isleaf)    {
  459.         // --- current key is not in a leaf
  460.         Key *ky = (Key *) (trnode->currkey->PrevListEntry());
  461.         if (ky != NULL)
  462.             currnode = ky->lowernode;
  463.         else
  464.             currnode = trnode->header.lowernode;
  465.           delete trnode;
  466.               trnode = new TNode(this, currnode);
  467.         // ----- go down to the leaf
  468.         while (!trnode->header.isleaf)    {
  469.             currnode =
  470.                 ((Key *)
  471.                 (trnode->keys.LastListEntry()))->lowernode;
  472.               delete trnode;
  473.                   trnode = new TNode(this, currnode);
  474.         }
  475.         // ---- use the last key in the leaf as the next one
  476.         trnode->currkey =
  477.             (Key *) (trnode->keys.LastListEntry());
  478.     }
  479.     else    {
  480.         // ------ current key is in a leaf
  481.         Key *thiskey = nullkey->Make();
  482.         *thiskey = *(trnode->currkey);
  483.  
  484.         // ----- point to the previous key in the leaf
  485.         trnode->currkey =
  486.             (Key *) (trnode->currkey->PrevListEntry());
  487.         while (trnode->currkey == NULL &&
  488.                         currnode != header.rootnode)    {
  489.             // --- current key was the first one in the leaf
  490.             TNode pnode(this, trnode->Parent());
  491.             pnode.SearchNode(thiskey);
  492.             if (pnode.currkey == NULL)
  493.                 pnode.currkey =
  494.                     (Key *) pnode.keys.LastListEntry();
  495.             else 
  496.                 pnode.currkey =
  497.                 (Key *) (pnode.currkey->PrevListEntry());
  498.             currnode = pnode.GetNodeNbr();
  499.             *trnode = pnode;
  500.         }
  501.         delete thiskey;
  502.     }
  503.     return Current();
  504. }
  505.  
  506.